package Topological;

import java.util.*;

public class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses]; // 统计每一个顶点的入度
        Map<Integer, List<Integer>> edges = new HashMap<>(); // 邻接表存图结构

        // 1.建图
        // 遍历所给课程, 构建邻接表
        for(int i = 0; i < prerequisites.length; i++) {
            // 拿到 a / b 课程
            // 注意题中意思是: 完成 a 之前要先完成 b
            // b -> a, 因此 key 是 b, value 是 a
            int a = prerequisites[i][0], b = prerequisites[i][1];
            if(!edges.containsKey(b)) {
                edges.put(b, new ArrayList<>());
            }
            edges.get(b).add(a);
            in[a]++; // a 的入度 + 1
        }

        // 2.拓扑排序
        Queue<Integer> queue = new LinkedList<>();
        //  (1) 找到入度为 0 的顶点, 放入队列中
        for(int i = 0; i < numCourses; i++) {
            if(in[i] == 0) {
                // 入度为 0 的顶点是 i, 因此放 i
                // (本题的课程是由 0 到 numCourses - 1, 因此记录入度的数组也算是一个哈希表了, 下标就是其课程)
                queue.offer(i);
            }
        }

        //  (2) BFS
        while(!queue.isEmpty()) {
            // 取出入度为 0 的点
            int b = queue.poll();
            // 删除该点的出度(即其他节点的入度)
            for(int a : edges.getOrDefault(b, new ArrayList<>())) {
                // 取出 b 的出度顶点 a
                // a 的入度 -1
                in[a]--;
                if(in[a] == 0) {
                    // 如果 a 的入度变为 0, 再次入队列
                    queue.offer(a);
                }
            }
        }

        // 本题是判断是否有环, 如果经历上述逻辑, 入度数组中存在元素依旧不为0, 说明有环
        for(int x : in) {
            if(x != 0) {
                // 说明有环
                return false;
            }
        }
        return true;
    }
}
